AlgorithmsDivide and Conquer

Binary Search(이진탐색)

분할정복법, 알고리즘

Binary Search locates a key x in a stored (nondecreasing order) array by first comparing x with the middle item of the array. If they are equal, the algorithm is done. If not, the array is divided into two subarrays, one containing all the items to the left of the middle item and the other containing all the items to the right. If x is smaller than the middle item, this procedure is then applied to the left subarray. Otherwise, it is applied to the right subarray. If they are equal, the algorithm is done. If not, the subarray is divided in two. This procedure is repeated until x is found or it is determined that x is not in the array.

이진탐색은 정렬된 배열에서 x를 찾기 위해 중간항목과 값을 비교한다. 만일 값이 일치하면 알고리즘은 종료되지만 그렇지 않은 경우, 해당 배열을 두 개의 부분배열로 나누고 x가 중간항목보다 작으면 왼쪽 부분배열에, 큰 경우 오른쪽 부분배열에 같은 비교절차를 적용한다.

일치하면 알고리즘은 완료되나 그렇지 않은 경우, x가 발견되거나 x가 배열에 없다고 결정될 때까지 상기 과정을 반복한다.

Example The steps done when sorting with Binary Search. (x=18)


Binary Search Algorithm

Algorithm Design

If x equals the middle item, quit. Otherwise:

  1. Divide the array into two subarrays about half as large. If x is smaller than the middle item, choose the left subarray. If x is larger than the middle item, choose the right subarray.
  2. Conquer(solve) the subarray by determining whether x is in that subarray.
  3. Unless the subarray is sufficiently small, use recursion to do this. Obtain the solution to the array from the solution to the subarray.

Pseudo Code

// Binary Search (Recursive)
index binsearch(index low, index high)
// Problem: Determine whether x is in the sorted array S of size n.
// Inputs: positive integer n, sorted array of keys S indexed from
// 1 to n, a key x.
// Outputs: location, the location of x in S (0 if x is not in S).
{
    index mid;

    if (low > high) // stopping case
        return 0;

    else
    {
        mid = (low + high) / 2;

        if (x == S[mid])
            return mid;
        else if (x < S[mid])
            return binsearch(low, mid - 1); // left subarray
        else
            return binsearch(mid + 1, high); // right subarray
    }
}
// Binary Search (Iteration)
void binsearch(int n, const keytype S[ ], keytype x, index& location)
// Problem: Determine whether x is in the sorted array S of size n.
// Inputs: positive integer n, sorted array of keys S indexed from
// 1 to n, a key x.
// Outputs: location, the location of x in S (0 if x is not in S).
{
    index low, high, mid;

    low = 1;
    high = n;
    location = 0;

    while (low <= high && location == 0)
    {
        mid = (low + high) / 2;
        if (x == S[mid])
            location = mid;

        else if (x < S[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
}

Source Code

// File: binsearch.h
#ifndef BINSEARCH_H
#define BINSEARCH_H

namespace algorihtms
{
    void binsearch1(const int S[ ], int first, int size, int target,
                    bool& found, int& location);
    // Problem: Determine whether x is in the sorted array S of size n.
    // Inputs: positive integer n, sorted array of keys S indexed from
    // 1 to n, a key x.
    // Outputs: location, the location of x in S (0 if x is not in S).

    void binsearch2(const int S[ ], int size, int target,
                    bool& found, int& location);
    // Problem: Determine whether x is in the sorted array S of size n.
    // Inputs: positive integer n, sorted array of keys S indexed from
    // 1 to n, a key x.
    // Outputs: location, the location of x in S (0 if x is not in S).
}

#endif
// File: binsearch.cpp
// Binary Search (Iteration)
# include "binsearch.h"

namespace algorihtms
{
  // Binary Search (Recursive)
  void binsearch1(const int S[ ], int first, int size, int target,
                  bool& found, int& location)
  {
    int mid;

    if (size == 0)
      found = false;
    else
    {
      mid = first + size/2;
      if (target == S[mid])
      {
        location = mid;
        found = true;
      }
      else if (target < S[mid])
        // The target is less than S[mid], so search before the mid
        binsearch1(S, first, size/2, target, found, location);
      else
        // The target must be greater than S[mid], so search after the mid
        binsearch1(S, mid+1, (size-1)/2, target, found, location);
    }
  }

  // Binary Search (Iteration)
  void binsearch2(const int S[ ], int size, int target,
                  bool& found, int& location)
  {
    int low, high, mid;

    low = 0;
    high = size;
    location = 0;
    found = false;

    while (low < high && location == 0)
    {
      mid = (low + high) / 2;
      if (target == S[mid])
      {
        location = mid;
        found = true;
      }

      else if (target < S[mid])
        high = mid - 1;
      else
        low = mid + 1;
    }
  }
}
// File: searchtest.cpp
#include <cstdlib>    // Provides EXIT_SUCCESS, int
#include <iostream>   // Provides cin, cout
#include "binsearch.h"
using namespace std;
using namespace algorihtms;

int main( )
{
    const int MANY = 13;
    int example[MANY] = {10, 12, 13, 14, 18, 20, 25, 27, 30, 35, 40, 45, 47};
    int target = 0;
    int location = 0;
    bool found = false;

    target = 25;
    binsearch1(example, 0, MANY, target, found, location);

    if (found)
        cout << target << " is at ["
             << location << "] in my array." << endl;
    else
        cout << target << " does not exists." << endl;

    target = 18;
    binsearch2(example, MANY, target, found, location);

    if (found)
        cout << target << " is at ["
             << location << "] in my array." << endl;
    else
        cout << target << " does not exists." << endl;

    return EXIT_SUCCESS;
}


Time Complexity Analysis

Basic operation

  • the comparison of x with S[mid]

Input size

  • n, the number of items in the array

Worst-Case Time Complexity

  • $W(n) = logn + 1 \in \Theta (logn)$
Share